package mtest3.day6;

import java.util.Arrays;

public class Demo1 {

    //堆排序
    public static void main(String[] args) {
        int[] arr = new int[]{22, 15, 17, 16, 14, 8, 12, 1, 25, 19, 33};
        heap_sort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void heap_sort(int[] arr) {
        //获取长度
        int len = arr.length; //11

//        从最后一个非叶子节点 开始倒序遍历   i  43210
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, len);
        }

        //倒序遍历整个数
        for (int i = len - 1; i >= 0; i--) {
            //把根节点和最后一个节点交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    //
    public static void adjustHeap(int[] arr, int i, int length) {
        int j = 2 * i + 1; //左孩子位置
        int temp = arr[i];//记录下i位置的元素

        while (j < length) {//只要j位置有节点，就继续比对s
            if (j + 1 < length && arr[j + 1] > arr[j]) {//右孩子存在并且右孩子更大
                j = j + 1;//把j指向j+1，指向右孩子
            }
            //把j位置的数据和之前保存的i位置的数据比较
            if (arr[j] > temp) {
                //孩子的数据大 就让i位置的数据等于这个孩子的数据
                arr[i] = arr[j];
                i = j; //把i移动到j的位置 继续调整
                j = i * 2 + 1; //更新j为新的左孩子的位置
            } else {
                //否则说明 i位置的数据是最大 调整完毕
                break;
            }
        }
        //把temp的值 赋值到i位置
        arr[i] = temp;
    }

}
